The present invention relates to a method of processing a digital signal and an apparatus therefor, and particularly to an improvement of a multiplying system in operational processing including a plurality of integrated multipliers, for example, in digital signal processing by means of digital filters, digital signal processors, etc.
Use of Booth's algorithm is well known for making the speed of the partial product adding process high in conventional multipliers (for example, reference is made to "Digital Signal Processing Handbook", edited by the Institute of Electronics, Information and Communication Engineers of Japan, Chapter 3; Japanese Patent Post-Examination No. Sho-57-28129; Japanese Patent Unexamined Publication No. Hei-4-67227; Japanese Patent Post-Examination No. Hei-2-30531; Japanese Patent Post-Examination No. Sho-62-17770; and so on). This algorithm will be described briefly by way of example in which partial products are generated by the secondary Booth's algorithm. In the form of expression with complement of "2", a multiplier Y is expressed by the following expression 1: ##EQU1## in which y.sub.n is a code bit, and y.sub.n-1 to y.sub.1 are numeric portions. Assuming the length n of Y is an even number and y.sub.0 =0 for the sake of simplification, the above expression can be made into the following expression 2. ##EQU2##
Assuming a multiplicand is X, the multiplication P=X.multidot.Y is expressed by the following expression 3: ##EQU3##
Therefore, the product P can be obtained by summing n/2 partial products (y.sub.2i +y.sub.2i+1 -2y.sub.2i+2)X.multidot.2.sup.2i. Here, 2.sup.2i corresponds to the weight of a bit. Since (y.sub.2i +y.sub.2i+1 -2y.sub.2i+2) takes any of 0, .+-.1, and .+-.2 in accordance with the values of the three bits y.sub.2i, y.sub.2i+1 and y.sub.2i+2, each partial product takes any of 0, .+-.X, and .+-.2X. In this case, 2X is the double of the multiplicand, and therefore it can be produced by shifting the multiplicand by one bit. The negative values can be produced by such a manner, for example, in which the complement of X (X (this X is expressed sometime as /X(X bar), but it is expressed in the present specification merely as X) is produced temporarily, and "1" (one) is added to its LSB (least significant bit). According to such Booth's algorithm, partial products can be obtained in the form including a code bit without specially dealing with a code bit in the expression with complement of "2", so that a correction circuit is not necessary, and there is a large advantage in construction of a hardware. In this algorithm, the input signals y.sub.2i, y.sub.2i+1 and y.sub.2i+2 are virtually decoded so as to be converted into an output signal B which is 0, .+-.1 or .+-.2. A signal processing block on a hardware performing this processing is a Booth decoder.
FIGS. 3 and 4 are circuit diagrams illustrating an example of the configuration of parallel multipliers for executing such Booth's algorithm. These circuit diagrams show an example of processing a multiplier Y (=y.sub.0 y.sub.1 y.sub.2 y.sub.3 y.sub.4 y.sub.5 y.sub.6 y.sub.7) and a multiplicand X.sub.k (=x.sub.0 x.sub.1 x.sub.2 x.sub.3 x.sub.4 x.sub.5 x.sub.6 x.sub.7) each of which has eight figures. The reference numeral 6.sub.k (k=1, 2, . . . , n) represents a block for executing Booth's algorithm, that is, a Booth decoder, which is constituted by elemental decoders 6.sub.kh (h=1, 2, 3, 4). The respective elemental decoders are also Booth decoders, but they are expressed by elemental decoders for the sake of convenience in order to avoid the complication of the term. Each elemental decoder 6.sub.kh has a function to decide which one of the values 0, .+-.1 and .+-.2 should be a coefficient for generating a partial product by y.sub.p-1, y.sub.p and y.sub.p+1 (P=0, 1, 2, . . . 6; y-1=0) corresponding to y.sub.2i, y.sub.2i+1 and y.sub.2i+2, and outputs a signal B (=(x, 2x, comp)).
FIG. 5 is a circuit diagram of a typical example of a Booth decoder. Although there are various Booth decoders including that which is disclosed in Japanese Patent Unexamined Publication No. Sho-62-29334, the Booth decoder of FIG. 5 will be described herein by way of example. In FIG. 5, y.sub.2i, y.sub.2i+1 and y.sub.2i+2 are inputted correspondingly to inputs 1, 2 and 3, and a signal B is outputted in accordance with the combination of the input values. Table 1 shows this relationship between the input and output the form of a truth table.
TABLE 1 ______________________________________ TRUTH TABLE Input 3 Input 2 Input 1 X 2X comp ______________________________________ 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 1 0 1 0 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 1 1 1 1 0 0 1 ______________________________________
Now return to FIGS. 3 and 4 again. Each of the partial product generating circuit group 7.sub.h (h=1, 2, 3, 4) generates a partial product of X and Y in accordance with the signal B. Each partial product generating circuit group 7.sub.h includes nine partial product generating circuits 7.sub.hg (g=1, 2, . . . , 9). In FIG. 3, however, those in only the case of g=1 or 2 are numbered in order to facilitate understanding of the drawing. The operation of a partial product generating circuit 7.sub.hj will be described with reference to FIGS. 6 to 8. If the signal B is (x, 2x, comp)=(1, 0, 0), the value of an element x.sub.i of a multiplicand X.sub.k is supplied to the partial product generating circuit 7.sub.hj. If the signal B is (x, 2x, comp)=(0, 1, 0), an element x.sub.i-1 is supplied to the partial product generating circuit 7.sub.hj. In the case of 2X=1 in the partial product generating circuit 7.sub.h1, a grounded portion becomes the input of lower bits. In the case of comp=1, "1" is added to the LSB of the partial product to form a complement of X or 2X. Output signals of the partial product generating circuits 7.sub.1 and 7.sub.2 are added by a half adder 8 which is connected those partial product generating circuits 7.sub.1 and 7.sub.2 through bus wiring. An output signal of the partial product generating circuit 7.sub.3 is added to a branch output signal of the half adder 8 by a hole adder 9.sub.1 which is connected to the partial product generating circuit 7.sub.3 and the half adder 8 through bus wiring. An output signal of the partial product generating circuit 7.sub.4 is added to a branch output signal of the half adder 9.sub.1 by a whole adder 9.sub.2 which is connected to the partial product generating circuit 7.sub.4 and the half adder 9.sub.1 through bus wiring. Finally a branch output signal of the partial product generating circuit 7.sub.1, branch output signals of the half adder 8 and the hole adder 9.sub.1, and an output signal of the hole adder 9.sub.2 are added to each other by a carry look ahead (CLA) 10, and an output of the carry look ahead (CLA) 10 is outputted as a multiplication signal Z.sub.k. The respective input and output terminals of the half adder 8, the whole adders 9.sub.1 and 9.sub.2, and the carry look ahead 10 are arranged as illustrated in FIGS. 9 to 11.
Thus an ordinary multiplier is constituted by a Booth decoder block and the other block 11 (hereinafter called "product addition block") including the block of a partial product generating circuit. Specifically, various configurations thereof are disclosed in Japanese Patent Unexamined Publication No. Sho-57-141753, No. Sho-61-246837, No. Sho-62-22146, No. Sho-62-216035, No. Sho-63-78229, No. Sho-63-78230, No. Sho-63-83834, No. Sho-63-286933, No. Hei-4-37211, No. Hei-4-186428, and so on.
On the other hand, a multiplier is indispensable in a digital signal processing technique such as a digital filter, a digital signal processor, or the like, and a plurality of multipliers are often included in one apparatus.
FIG. 12 is a block diagram illustrating a circuit configuration of a conventional digital filter called a direct type. In this filter, an input signal X is supplied from an input terminal 1, and on the way of the input signal X to pass through a plurality of delay elements 2, the output signals X.sub.k of the respective delay elements 2.sub.k-1 (k=1, 2, . . . , i, . . . , n; 2.sub.0 means no delay) and a discrete variable Y are processed along the Booth's algorithm in each multiplier 1.sub.k. In this case, the signal Y is decoded by a Booth decoder 6.sub.k in the multiplier 1.sub.k, and a multiplication value Z.sub.k is generated by signal processing based on the decoded signal and the signal X. The values Z.sub.k are added totally in an adder 3. The adder 3 outputs a filtered signal C to its output terminal. The signal Y is supplied from a terminal 2 so as to be temporarily accumulated in each of storage elements 4 such as registers. The operation timing of each storage element 4.sub.k is controlled by an address decoder 5.
In the case of a digital filter of this type, we call the unit consisting of delay element 2.sub.i, the multiplier 1.sub.i having the Booth decoder 6.sub.i and the memory element 4.sub.i "i-th stage filter unit (i=1, 2, . . . n) for conveniences sake. Then, it can be thought that the apparatus indicated in FIG. 12 is an apparatus in which n pieces of filter units are connected in series and the output signals Z.sub.j (j=1, 2, . . . n) from each stage can be added by a single adder 3.
FIG. 13 is a block diagram illustrating the circuit configuration of a conventional digital filter called transposition type. A unit constituted by a storage element 4.sub.k, a multiplier 1.sub.k, an adder 3.sub.k and a delay element 2.sub.k is named "k-th stage filter unit" for the sake of convenience in description. First in the k-th stage filter unit(k=1, 2, . . . i,..n), a signal X is supplied to the multiplier 1.sub.k while another input signal Y is supplied to the multiplier 1.sub.k through the storage element 4.sub.k. The two signals are processed along the Booth's algorithm in the multiplier 1.sub.k. In this case, the signal Y is decoded by the Booth decoder 6.sub.k in the multiplier 1.sub.k, and a multiplication value Z.sub.k is generated by signal processing based on the decoded signal and the signal X. The multiplication value Z.sub.k is supplied to the adder 3.sub.k from the multiplier 1.sub.k and added to a signal Z.sub.bk-1 from the (k-1)-th stage filter unit, and the result of addition is supplied to the delay element 2.sub.k as a signal Z.sub.ak.
As a result, the signal Z.sub.ak becomes a delayed signal Z.sub.bk. In the same manner, in the following stage, the (k+1)-th stage filter unit, the signal X is supplied to the multiplier 1.sub.k+1 while another signal Y is supplied to the multiplier 1.sub.k+1 through the storage element 4.sub.k+1. The two signals are processed along the Booth's algorithm in the multiplier 1.sub.k in the same manner as in the case of the k-th stage filter unit so that a multiplication value Z.sub.k+1 is generated. The multiplication value Z.sub.k+1 is supplied to the adder 3.sub.k+1 from the multiplier 1.sub.k+1 and added to the signal Z.sub.bk from the k-th stage filter unit, the result of addition being supplied, as a signal Z.sub.ak+1, to the delay element 2.sub.k+1. As a result, the signal Z.sub.ak+1 becomes a delayed signal Z.sub.bk+1. The same operation is repeated in each filter unit, and finally a filtered signal C is outputted.
The respective operation timings of the delay element 2 and the storage element 4 in each filter unit are controlled by a clock signal CLK. The operation timing in each filter unit and the operation timing between filter units can be attained under the above-mentioned control by the clock signal CLK and in a cycle taking into consideration the signal delay produced in each filter unit. A signal Z.sub.b0 other than a signal Z.sub.1 is supplied to an adder 3.sub.1, while the signal Z.sub.b0 is assumed to be a grounded signal in the above description.
The above examples are merely typical ones, but it is understood therefrom that a digital filter includes a number of multipliers. Further, being represented by these examples, it has been general that in a multiplication system a plurality of multipliers are connected in parallel to thereby increase the speed of operation.
In a conventional digital signal processing method or in a conventional digital signal processing apparatus, a Booth decoder is included in each multiplier itself. Accordingly, in the case using a plurality of multipliers to performing digital signal processing, the Booth's algorithm is executed in an overlapping manner in the respective multipliers. For example, in a conventional digital filter, individual Booth decoders 6.sub.k or elemental decoders 6.sub.kh are operated in an overlapping manner respectively in a plurality of multipliers connected in parallel to each other. This is vain in the quantity of operation of the system as a whole. Further, each multiplier includes a Booth decoder having the same function, so that the hardware is made complicated in Structure in vain. Further, in the case where it is intended to realize higher speed signal processing, the process of multiplication itself limits the speed of the signal processing, so that there occurs a limit in the signal band which can be processed to thereby make the field of utilization narrower in vain.
Particularly there is a case where the operation time of each multiplier becomes a problem when a digital signal processing system is constituted by combination of a plurality of multipliers. In the case of, for example, a digital filter in which multipliers are parallelly connected so that an output signal from each multiplier is used in the succeeding signal processing, it is required so that the signal inputting cycle and the signal processing timing accord with each other, and the digital signal processing cannot be executed if this timing is out of order. In such a digital signal processing system, therefore, it is necessary to make the operation time of each multiplier shorter than the cycle of the signal inputting.
However, high speed operation is difficult since the delay of a signal is produced bit by bit in respective Booth decoders if the Booth decoders are operated in parallel or in an overlapping manner in multipliers as in the conventional case. Particularly in the case of performing higher speed processing, production of a slight delay becomes a large obstacle on signal processing. Such a problem in high speed processing is more conspicuous in a transposition type shown in FIG. 13 than in a transversal type shown in FIG. 12. This is because the number of constituents is larger in the transposition type of FIG. 13, so that it is necessary to perform operation timing adjustment not only in each filter unit constituted by a storage element 4.sub.k, a delay element 2.sub.k, a multiplier 1.sub.k and an adder 3.sub.k, but also between filter units. In view of the expansion of new fields of applications such as audio processing, video processing, and so on, and the development of multi-media, etc., it is strongly demanded to make the speed of the digital signal processing higher.